class Solution {
public:

    // 法一：排序，对比数组
    // int findUnsortedSubarray(vector<int>& nums) {
    //     vector<int> new_vec(nums.begin(), nums.end());
    //     sort(new_vec.begin(), new_vec.end());
    //     int start = -1;
    //     int end = -2;
    //     for (int i = 0; i < nums.size(); ++i) {
    //         if (new_vec[i] != nums[i]) {
    //             if (start == -1) start = i;
    //             end = i;
    //         }
    //     }
    //     return end - start + 1;
    // }

    // 法二：维护min max,在一次循环中同时完成左右边的计算
    int findUnsortedSubarray(vector<int>& nums) {
        int n = nums.size();
        int min = INT_MAX;
        int max = INT_MIN;
        int start = -1;
        int end = -2;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] >= max) {
                max = nums[i];
            } else {
                end = i;
            }
            if (nums[n - i - 1] <= min) {
                min = nums[n - i - 1];
            } else {
                start = n - i - 1;
            }
        }
        return end - start + 1;
    }
};